package arithmetic.LeetCode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import utils.TreeNode;

/**
 * 二叉树的中序遍历
 * @author jiangfeng on 2023/6/13
 */
public class InorderTraveral {
    public static void main(String[] args) {
        System.out.println(new Solution().inorderTraversal(TreeNode.createTree(1,null,2,3)));
    }
    static class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList();
            Stack<TreeNode> stack = new Stack();
            TreeNode index = root;
            while(index!=null||!stack.empty()){
                if(index!=null ){
                    if( index.left!=null){
                        stack.push(index);
                        index=index.left;
                    }else {
                        // 当前没有左值了,先放进去.
                        res.add(index.val);
                        index=index.right;
                    }
                    continue;
                }

                if (!stack.isEmpty()){
                    TreeNode father = stack.pop();
                    // 中间可以放了
                    res.add(father.val);
                    // 指针去右边.
                    index=father.right;
                }

            }

            return res;
        }

        public List<Integer> inorderTraversal2(TreeNode root) {
            List<Integer> res = new ArrayList();
            inorderTraversal(root,res);
            return res;
        }
        public void inorderTraversal(TreeNode root,List<Integer> res){
            if(root!=null){
                inorderTraversal(root.left,res);
                res.add(root.val);

                inorderTraversal(root.right,res);
            }

        }

    }
}
